//
//  ProblemMS1713.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/4/3.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 面试题 17.13. 恢复空格
 哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。

 注意：本题相对原题稍作改动，只需返回未识别的字符数

 示例：
     输入：
     dictionary = ["looked","just","like","her","brother"]
     sentence = "jesslookedjustliketimherbrother"
     输出： 7
     解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。
     提示：

     0 <= len(sentence) <= 1000
     dictionary中总字符数不超过 150000。
     你可以认为dictionary和sentence中只包含小写字母。
 */
@objcMembers class ProblemMS1713: NSObject {
    func solution() {
        print(respaceTrie(["looked","just","like","her","brother"], "jesslookedjustliketimherbrother"))
        print(respaceTrie(["jxnonurhhuanyuqahjy","phrxu","hjunypnyhajaaqhxduu"], "qahurhoharrdjxnonurhhuanyuqahjyppnha"))
        print(respaceTrie(["axxpxakkxktpa","aappk","kddxxp","p","atxtdtpkt","ptxkatdakp","padpatxaptpaatkadaxka","xd","xa","kptkaxxpptpkxaxtx","t","atdxkttpppakkxkxpxdxxapakaadaxkakapxptdpkxkaadtx","kp","xa","pkkataxkakkxxktxxdptatkkxta","dxttapxpxkxttkktpkx","tat","txpdakdxpaa","axxkaxkxkkkdpkpttxdkpaaakkakdkkdxatd","paxaa"],
                          "ppkaxpxddkpaatttxtpdtaxtadxaxatxtdtpktdxpppkaxpxddkpaatttxtpdtaxtadx"))
    }
    
    /*
     ppkaxpxddkpaatttxtpdtaxtadxaxatxtdtpktdxpppkaxpxddkpaatttxtpdtaxtadx
     00kax000d00aa000x00d0ax0ad00x000000000dx000kax000d00aa000x00d0ax0adx
     00kax000d00aa000x00d0ax0ad00x000000000dx000kax10101110999877776665543321
     kax d aa x d ax ad x dx kax d aa x d ax adx
     */
    
    /*
     动态规划：超时，在判断是否在字典中，需要剪枝
     1: 创建一个数组dp[len]
     2: dp[i]：表示从[i～len]包含的没匹配的字符数，那么dp[0]就是题解
     3: 求dp[0]的值，
        3.1 取第一个字符：s[0] 是否在字典中：在 dp[0] = 0 + dp[1], 不在 dp[0] = 1 + dp[1]
        3.2 取前二个字符：s[0-1] 是否在字典中：在 dp[0] = 0 + dp[2], 不在 dp[0] = 2 + dp[2]
        ..... 取最小值
     */
    func respace(_ dictionary: [String], _ sentence: String) -> Int {
        let charts = Array(sentence)
        var dp = Array(repeating: -1, count: sentence.count)
        
        return respaceDG(dictionary, &dp, 0, charts)
    }
    
    func respaceDG(_ dictionary: [String], _ dp: inout [Int] , _ start: Int, _ charts: [Character]) -> Int {
        if start >= charts.count {
            return 0
        }
        if dp[start] != -1 {
            return dp[start]
        }
        
        var result = Int.max
        var str = ""
        for i in start..<charts.count {
            
            str.append(charts[i])
            if dictionary.contains(str) == true {
                result = min(result, respaceDG(dictionary, &dp, i+1, charts))
            } else {
                result = min(result, i - start + 1 + respaceDG(dictionary, &dp, i+1, charts))
            }
        }
        
        dp[start] = result
        return result
    }
    

    /*
     使用Trie树进行剪枝
     Trie树：创建一个根，里面包含一个数组s[26],  然后对字典的每个将字符串依次遍历，根据首字母放入数组中
     例如字典是：[a, an, abd, good, rest, ge]
     那么Trie树的结构就是：
                          根
                      /  \   \
         dic[0]      a    r   g
                    / \    \   \  \
         dic[1]    n   b    e   e  o    dic[5]
                        \    \      \
                 dic[2]  d    s      o
                               \      \
                        dic[4]  t      d dic[3]
     1: 创建一个数组list[len]
     然后倒叙遍历字符串sentence：jesslookedjustliketimherbrother
     1: 查看最后一个r是否在字典中，在dp[len-1] = 0, 不在dp[len-1] = 1
     .....
     2: 查看最后第i个字符:e， 查看从e开头的单词，最大的长度，
        2.1 不存在以e开头的单词，那么dp[i] = 1 + dp[i+1],
        2.2 存在最长的单词是‘e’,长度就是1: dp[i] = dp[i+1]
        2.2 存在最长的单词是‘er’,长度就是2: dp[i] = dp[i+2]
     
     */
    func respaceTrie(_ dictionary: [String], _ sentence: String) -> Int {
        if sentence.count == 0 {
            return 0
        }
        // 创建一个Trie树
        let dot = Trie()        // 根
        for dic in dictionary {
            dot.add(dic)
        }

        let charts = Array(sentence)
        var list = Array(repeating: 0, count: sentence.count+1)
        
        // 字符串倒叙遍历
        for i in (0..<charts.count).reversed() {
            var g: Trie? = dot             // 根
            var j = i
            
            var n = 1 + list[i+1]
            while j < charts.count, g != nil {
                if (g!.next[charts[j].asciiValue!] == nil) {
                    break
                }
                
                g = g!.next[charts[j].asciiValue!]
                j += 1
                if g!.end == true {
                    if j < charts.count {
                        n = min(n,  list[j])
                    } else {
                        n = 0
                    }
                }
            }
            list[i] = n
        }
        
        print(list)
        return list[0]
    }
}

class Trie: NSObject {
    var next: [UInt8 : Trie] = [:]            // key: ascii
    var end = false
    
    func add(_ s: String) {
        var cur = self
        for c in s {            // 对字符串的每个字符都创建一个Trie
            if cur.next[c.asciiValue!] == nil {
                cur.next[c.asciiValue!] = Trie()
            }
            cur = cur.next[c.asciiValue!]!
        }
        cur.end = true
    }
    
}
